package dp;

/**
 * @author: june
 * @date: 2023/8/7
 * @description: 746. 使用最小花费爬楼梯
 * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 * 请你计算并返回达到楼梯顶部的最低花费。
 **/

public class MinCostClimbingStairs_746 {
    public static void main(String[] args) {
        MinCostClimbingStairs_746 minCostClimbingStairs_746 = new MinCostClimbingStairs_746();
        int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
        minCostClimbingStairs_746.minCostClimbingStairs(cost);
    }

    public int minCostClimbingStairs(int[] cost) {
        // 1、dp数组，dp[i]表示爬到第i阶楼梯支付的最小总费用
        int[] dp = new int[cost.length + 1];

        // 2、初始化dp数组
        // 如果选择从第0阶开始，此时不消耗，往上爬才消耗
        dp[0] = 0;
        // 如果从第1阶开始，直接到达，，此时不消耗，往上爬才消耗
        dp[1] = 0;

        // 3、递推公式
        // 到达第i步，有2种方式
        // 先到i-2步，再一次爬2个台阶，到达第i步，dp[i] = dp[i-2] + cost[i-2]
        // 先到i-1步，再一次爬1个台阶，到达第i步，dp[i] = dp[i-1] + cost[i-1]
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
        }
        return dp[cost.length];
    }
}
